729B - Spotlights - CodeForces Solution

#include <bits/stdc++.h>

using namespace std;

const int MAX = 1e3 + 2;

bool tab[MAX][MAX];
bool l[MAX][MAX];
bool r[MAX][MAX];
bool u[MAX][MAX];
bool d[MAX][MAX];

using ll = long long;

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m;
  cin >> n >> m;

  for(int i = 1; i <= n; i++)
    for(int j = 1; j <= m; j++)
      cin >> tab[i][j];

  for(int i = 1; i <= n; i++)
  {
    for(int j = 1; j <= m; j++)
    {
      l[i][j] = l[i][j-1] || tab[i][j];
      u[i][j] = u[i-1][j] || tab[i][j];
    }
  }

  for(int i = n; i > 0; i--)
  {
    for(int j = m; j > 0; j--)
    {
      r[i][j] = r[i][j+1] || tab[i][j];
      d[i][j] = d[i+1][j] || tab[i][j];
    }
  }

  ll ans = 0;

  for(int i = 1; i <= n; i++)
  {
    for(int j = 1; j <= m; j++)
    {
      if(!tab[i][j])
      {
        ans += l[i][j-1];
        ans += r[i][j+1];
        ans += u[i-1][j];
        ans += d[i+1][j];
      }
    }
  }

  cout << ans << endl;

  return 0;
}